﻿using System;
using System.Collections.Generic;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.Problems.SpanningTrees.Kruskal;
using System.Linq;
using Algoritmia.Problems.Traversals;

namespace Algoritmia.Problems.TravelingSalesPerson
{
    public class SpanningTreeTravelingSalesPerson : ITravelingSalesPerson
    {

        #region Implementation of ITravelingSalesPerson

        public IEnumerable<Tuple<double, double>> Travel(DataStructures.Lists.IList<Tuple<double, double>> points)
        {
            var list = (from a in points
                        from b in points
                        where a.Item1 != b.Item1 || a.Item2 != b.Item2
                        select
                            new Tuple
                            <Tuple<double, double>,
                            Tuple<double, double>>(a, b)).ToList();

            var G = new UndirectedGraph<Tuple<double, double>>(edges: list );

            var tree = new KruskalMinimumSpanningForestFinder<Tuple<double, double>>().MinimumSpanningForest(G, (a, b) =>
                                                                                        {
                                                                                            var x = a.Item1 - b.Item1;
                                                                                            var xx = x*x;
                                                                                            var y = a.Item2 - b.Item2;
                                                                                            var yy = y*y;
                                                                                            return Math.Sqrt(xx + yy);
                                                                                        });
            var MST = new UndirectedGraph<Tuple<double, double>>(points, tree);
            var dft = new DepthFirstTraverser<Tuple<double,double>,Tuple<double,double>>();
            foreach(var e in dft.Traverse(MST,points[0],(a,b) => b))
            {
                yield return e;
            }
            yield return points[0];
        }

        #endregion
    }
}
